package 堆;

public class HeapOperation {
    public static void shiftDown(long[] array, int size, int index){
        while (true){
            int leftIndex = 2 * index + 1;
            if (leftIndex >= size){
                return;
            }

            int rightIndex = leftIndex + 1;
            int minIndex = leftIndex;
            if (rightIndex < size && array[rightIndex] < array[leftIndex]){
                minIndex = rightIndex;
            }

            if (array[index] <= array[minIndex]){
                return;
            }

            long t = array[index];
            array[index] = array[minIndex];
            array[minIndex] = t;

            index = minIndex;
        }
    }

    public static void creatHeap(long[] array, int size){
        // 找到第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
        for (int i = (size - 2) / 2; i >= 0; i--){
            shiftDown(array, size, i);
        }
    }

public static void shiftUp(long[] array, int index){
    while (index > 0){
        int parent = (index -  1) / 2;

        if (array[parent] < array[index]){
            return;
        }else {
            // 将双亲与孩子节点进行交换
            long t = array[index];
            array[index] = array[parent];
            array[parent] = t;

            index = parent;
            parent = (parent - 1) / 2;
        }
    }
}
}
